package com.singzi.leetcode.N700;

import java.util.Arrays;

public class T0686 {
    public static void main(String[] args) {
        String a = "abaababa" , b ="abaabaa";
        Solution0686 solution0686 = new Solution0686();
        System.out.println(solution0686.repeatedStringMatch(a, b));


    }
}
class Solution0686 {
    public int repeatedStringMatch(String a, String b) {
        int[] next = new int[b.length()];
        getNext(next, b);
        String temp = a;
        for (int i = 0; i < 10000; i++) {
            if(strStr(temp,b,next)){
                return i+1;
            }
            temp = temp + a;
            if(temp.length() > 3*b.length()+3*a.length())
            {
                break;
            }
        }
        return -1;
    }
    public void getNext(int[] next, String s){

        int j = 0;
        next[0] = 0;
        for (int i = 1;i < s.length();i++)
        {
            while (j > 0&&s.charAt(i)!=s.charAt(j))
            {
                j = next[j-1];
            }
            if (s.charAt(i) == s.charAt(j))
            {
                j++;
            }

            next[i] = j;
        }

    }
    public boolean strStr(String haystack, String str, int[] next)
    {
        int j = 0;
        for(int i = 0; i<haystack.length(); i++)
        {
            while (j > 0 && str.charAt(j) != haystack.charAt(i))
            {
                j = next[j-1];
            }
            if(str.charAt(j) == haystack.charAt(i))
            {
                j++;
            }
            if (j == str.length())
            {
                return true;
            }

        }

        return false;
    }
}